package longestIncreasingPath;



public class Solution {
   int[] x = new int[]{-1,1,0,0};
   int[] y = new int[]{0,0,1,-1};
   int i,j,k;
   int[][] ans;
   int[][] mx;
  public  int longestIncreasingPath(int[][] matrix) {
	    if (matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
        ans =new int[matrix.length][matrix[0].length];
        mx=matrix;
        int max=1;

        for (i=0;i<matrix.length;i++)
        	for (j=0;j<matrix[0].length;j++)
              ans[i][j]=-23333;
      
        for (i=0;i<matrix.length;i++)
        	for (j=0;j<matrix[0].length;j++)
        		max=Integer.max(max,dfs(i,j));


           return max;   
    }
  private  int dfs(int i, int j) {
	if (ans[i][j]!=-23333) return ans[i][j];
	ans[i][j]=1;
	for (int k=0;k<=3;k++){
        if ((i+x[k]>=0) && (i+x[k]<ans.length))
      	  if ((j+y[k]>=0) && (j+y[k]<ans[0].length))
      	   if (mx[i][j]<mx[i+x[k]][j+y[k]])
      		   ans[i][j]=Integer.max(ans[i][j], dfs(i+x[k],j+y[k])+1);
	}
     return ans[i][j];
} 
}


/* 
 * 329. Longest Increasing Path in a Matrix
 * DFS暖手题
 * 题目的奇葩要求。。
 * 意识到不是DP之后30min过去了卧槽。。
 * 简单的DFS+记忆化
 * 不需要处理逆序列情况
 * 以前刷过的题即视感太强烈导致错判(?)以后认真看题吧XD
 */
